

// 封装有头循环双向链表
public class MList implements StoreEngine {
    private Node head = new Node();
    private int length = 0;
    private Node travelId = null;
    static final private MList findArr = new MList();

    private class Node {
        Object data = null;
        Node next = null;
        Node prev = null;

        public Node() {}

        public Node(Node next, Node prev) {
            this.next = next;
            this.prev = prev;
        }

        public Node(Object data, Node next, Node prev) {
            this.data = data;
            this.next = next;
            this.prev = prev;
        }
    }

    public MList() {
        clean();
    }

    //构造方法，支持构造传入数据
    public MList(Object ... newData) {
        clean();
        append(newData);
    }

    //尾插数据
    public StoreEngine append(Object ... newData) {
        return add(length + 1, newData);
    }

    //头插数据
    public StoreEngine prepend(Object ... newData) {
        return add(1, newData);
    }

    //指定位置插入数据
    public StoreEngine add(int index, Object ... inputData) {
        //如果没有传入新数据，则不做任何操作
        if (inputData == null)
            return this;

        Node tail = null;

        if (index < 1) {
            tail = head;
        } else if (index > length) {
            tail = head.prev;
        } else {
            for (tail = head; --index != 0 && tail.next != head; tail = tail.next)
                ;
        }

        for (int i = 0; i < inputData.length; ++i) {
            Node newNode = new Node(inputData[i], tail.next, tail);
            tail.next.prev = newNode;
            tail.next = newNode;
            length++;
        }

        return this;
    }

    //返回数据个数
    public int len() {
        return length;
    }

    //返回第几个结点
    private Node _find(int index) {
        if (index < 1 || index > length)
            return null;

        Node tail = head.next;
        while (--index != 0 && tail != head) {
            tail = tail.next;
        }
        return tail;
    }

    // 返回第几个数据
    public Object find(int index) {
         Node tail = _find(index);
         return (tail == null) ? null : tail.data;
    }

    //返回第一个数据
    public Object first() {
        return (head.next == head) ? null : head.next.data;
    }

    // 返回最后一个数据
    public Object last() {
        return (head.prev == head) ? null : head.prev.data;
    }

    // 返回指定起始位置开始查找，并且指定返回查找到的结果个数
    public StoreEngine find(int start, int num, Object key, DataCompare cmpObj) {

        findArr.clean();

        Node tail = _find(start + 1);

        while (tail != head) {
            if (cmpObj.compare(key, tail.data) == 0) {
                findArr.append(tail.data);
                if (num != 0 && --num == 0) {
                    break;
                }
            }
        }
        return findArr;
    }

    // 返回查找到的第几个数据
    public Object findOf(int index, Object key, DataCompare cmpObj) {
        find(0, index, key, cmpObj);

        if (findArr.len() < index)
            return null;

        return findArr.last();

        // return find(0, index, key, cmpObj).last();
    }

    // 返回查找到的前几个数据
    public StoreEngine findNum(int num, Object key, DataCompare cmpObj) {
        return find(0, num, key, cmpObj);
    }

    // 返回查找到所有数据
    public StoreEngine findAll(Object key, DataCompare cmpObj) {
        return find(0, 0, key, cmpObj);
    }

    //对数据进行排序
    public StoreEngine sort(DataCompare cmpObj) {
        Object tmpData;
        Node t;

        for (Node i = head.next; i.next != head; i = i.next) {
            tmpData = i.data;
            t = i;
            for (Node j = i.next; j != head; j = j.next) {
                if (cmpObj.compare(j.data, tmpData) > 0) {
                    tmpData = j.data;
                    t = j;
                }
            }
            t.data = i.data;
            i.data = tmpData;
        }

        return this;
    }

    //根据结点删除
    private StoreEngine _delete(Node tail) {
        tail.next.prev = tail.prev;
        tail.prev.next = tail.next;

        tail.next = null;
        tail.prev = null;

        length--;

        return this;
    }

    //删除第几个数据
    public StoreEngine delete(int index) {
        if (index < 1 || index > length)
            return this;

        Node tail = head.next;

        while (--index != 0 && tail != head) {
            tail = tail.next;
        }

        return _delete(tail);
    }

    //删除查找到数据指定删除从第几个到多少个
    public StoreEngine delete(int start, int num, Object key, DataCompare cmpObj) {

        Node save = null;
        Node tail = _find(start + 1);

        while (tail != head) {
            save = tail.next;
            if (cmpObj.compare(key, tail.data) == 0) {
                // System.out.printf("=====> delet index = %d\n", i);
                _delete(tail);
                if (num != 0 && --num == 0)
                    break;
            }
            tail = save;
        }

        return this;
    }
    // 删除查找到的第几个数据
    public StoreEngine deleteOf(int index, Object key, DataCompare cmpObj) {
        Node tail = head.next;

        while (tail != head) {
            if (cmpObj.compare(key, tail.data) == 0 && --index == 0) {
                _delete(tail);
                break;
            }
            tail = tail.next;
        }

        return this;
    }

    //删除指定个数查找到的数据
    public StoreEngine deleteNum(int num, Object key, DataCompare cmp) {
        return delete(0, num, key, cmp);
    }

    public StoreEngine deleteAll(Object key, DataCompare cmp) {
        return delete(0, 0, key, cmp);
    }

    // 清空所有数据
    public StoreEngine clean() {
        head.next = head;
        head.prev = head;
        length = 0;
        travelId = null;
        return this;
    }

    // 遍历接口
    // 实现重置遍历标识
    public StoreEngine rewind() {
        travelId = null;
        return this;
    }

    // 返回下一个数据元素
    public Object getNext() {
        if (travelId == null) {
            travelId = head.next;
        }
        if (travelId == head) {
            travelId = null;
            return null;
        }
        travelId = travelId.next;
        return travelId.prev.data;
    }
}
